package com.zklh.leetcode.other.problem10;

class Solution {


    public boolean isMatch(String s, String p){
        return true;
    }

    /**
     * 用于匹配指定起始位置到末尾, 这里使用了动态规划和回溯算法的思想
     * @param regexArray 
     * @param targetArray
     * @param regexStartIndex 正则表达式当前匹配段的起始位置
     * @param targetStartIndex 目标字符串字符数组当前匹配段的起始位置
     * @return 返回匹配的结果
     */
    private boolean match(char[] regexArray, char[] targetArray, int regexStartIndex, int targetStartIndex){
        /* 这里是递归终止条件, 主要也是为了解决regexArray,targetArray某一个匹配到结尾的情况 */
        if (regexStartIndex > regexArray.length-1 && targetStartIndex > targetArray.length-1) {
            return true;
        }else if (regexStartIndex > regexArray.length-1) {
            return false;
        // 这里表示正则表达式剩余, 目标字符数组已经到结尾, 这里是有可能成功的, 如果剩余可以匹配空的情况如 .*,a*,结尾
        }else if (targetStartIndex > targetArray.length-1){
            if (matchNull(regexArray, targetStartIndex, targetArray.length-1)) {
                return true;
            }else {
                return false;
            }
        }

        /* 这里是清晰段匹配, 清晰段匹配需要额外考虑清晰段为空的情况 */
        // 获取当前层正则表达式数组对应的清晰匹配段的结束位置
        int regexClearEnd = truncateClear(regexArray, regexStartIndex);
        // 这里是清晰段匹配的结尾索引, 默认是起始位置-1
        int targetClearEnd = targetStartIndex - 1;
        // 这里考虑到清晰段为空的情况, 只有包含清晰段的时候, 才会进行清晰段匹配
        if(regexClearEnd != regexStartIndex - 1){
            // 用于匹配清晰段
            targetClearEnd = matchClear(regexArray, targetArray, regexStartIndex, regexClearEnd, targetStartIndex);
            // 匹配清晰段失败 直接返回false
            if (targetClearEnd == -1) {
                return false;
                // 两个数组有一个匹配到末尾, 直接进入下一层, 这里这样写是为了避免代码重复
            }else if (regexClearEnd == regexArray.length - 1 || targetClearEnd == targetArray.length-1) {
                return match(regexArray,targetArray,regexClearEnd+1,targetClearEnd+1);
            }
        }

        /* 模糊段匹配需要考虑调整的情况, 因为匹配默认是按照最大化匹配, 如果下层匹配不通过, 可以调整当前层再次进行下层匹配 */
        int targetDimStart = targetClearEnd + 1;
        int regexDimStart = regexClearEnd + 1;
        int regexDimEnd = truncateDim(regexArray, targetDimStart);

        // 进行模糊段的匹配
        int targetDimEnd = matchDim(regexArray, targetArray, regexDimStart, regexDimEnd, targetDimStart);
        if(targetDimEnd == -1){
            return false;
        }
        /* 这里进行失败调整,成功跳出循环,因为问题描述,只会存在*,.所以调整只需要匹配长度-1就可以 */
        // 判断是否可以调整
        boolean canAjust = '*' == regexArray[regexDimEnd];
        do {
            if (match(regexArray, targetArray, regexDimEnd+1, targetDimEnd+1)) {
                return true;
            }
        // 如果可以调整, 则可以调整到模糊匹配长度为0,这是因为模糊匹配只有* . 这两种字符
        }while (canAjust && targetDimEnd-- >= targetDimStart);
        return false;
    }

    /**
     * 从指定的起始位置开始截取, 这里用于截取清晰段, 也就是截取到.或者*前一位字符前,或者直到末尾
     * 这里有清晰段为空的情况, 这里返回start - 1
     * @param regexArray
     * @param regexClearStart
     * @return
     */
    private int truncateClear(char[] regexArray, int regexClearStart){
        // 提供一个默认值
        int regexClearEnd = regexClearStart-1;
        // 表示任何字符的符号
        char anyCharSign = '.';
        // 表示任何数目的符号
        char anyNumberSign = '*';
        for (int i = regexClearEnd+1; i < regexArray.length; i++) {
            if (regexArray[i] == anyCharSign) {
                regexClearEnd = i - 1;
                break;
            }else if(regexArray[i] == anyNumberSign){
                regexClearEnd = i - 2;
                break;
            }
        }
        return regexClearEnd;
    }

    /**
     * 用于截取模糊段
     * @param regexArray
     * @param regexDimStart
     * @return
     */
    private int truncateDim(char[] regexArray, int regexDimStart){

        return 1;
    }

    /**
     * 部分匹配, 用于匹配一部分匹配段
     * @param regex
     * @param target
     * @param regexStart
     * @param regexEnd
     * @param targetStart
     * @return 匹配字符串的末尾索引, 如果匹配失败, 返回-1
     */
    private int matchClear(char[] regex, char[] target, int regexStart, int regexEnd, int targetStart){
        return 0;
    }


    /**
     * 用于匹配模糊段
     * @param regex
     * @param target
     * @param regexStart
     * @param regexEnd
     * @param targetStart
     * @return
     */
    private int matchDim(char[] regex, char[] target, int regexStart, int regexEnd, int targetStart){
        return -1;
    }

    /**
     * 匹配null, 用于前缀匹配为true, 但正则表达式数组有剩余字符,此时使用
     * @param regex
     * @param start
     * @return
     */
    private boolean matchNull(char[] regex, int start, int end){
        return false;
    }


}
